package com.xiaoyu.backtracking;

import java.util.*;

/**
 * @program: DS_and_A
 * @description: 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 *  [1,2,1],
 *  [2,1,1]]
 *
 * @author: YuWenYi
 * @create: 2021-05-21 10:55
 **/
public class PermuteUnique_47 {
    public List<List<Integer>> permuteUnique(int[] nums) {
        int len = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        if (len == 0){
            return res;
        }
        // 排序（升序或者降序都可以），排序是剪枝的前提
        Arrays.sort(nums);

        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[len];

        dfs(nums, len, 0, used, path, res);

        return res;
    }

    public void dfs(int[] nums,int len,int depth,boolean[] used,Deque<Integer> path,List<List<Integer>> res) {
        if (len == depth) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < len; i++) {
            if (!used[i]) {
                // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
                //写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
                //特点是：假设num数组中数字1的顺序是:1、1'、1'' 那么最后出现的顺序只能是 1、1'、1''。
                if (i > 0 && nums[i] == nums[i-1] && !used[i-1]){
                    //System.out.println("被减掉的枝"+path);
                    continue;
                }
                used[i] = true;
                path.push(nums[i]);

                dfs(nums, len, depth + 1, used, path, res);

                used[i] = false;
                path.pop();
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 1,1, 2};
        PermuteUnique_47 solution = new PermuteUnique_47();
        List<List<Integer>> lists = solution.permuteUnique(nums);
        System.out.println(lists);
    }
}
